package com.backpack;

import java.util.List;

/**
 * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
 *
 * 输入: s = "leetcode", wordDict = ["leet", "code"]
 * 输出: true
 * 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
 */
public class WordBreak0113_139 {

    public boolean wordBreak(String s, List<String> wordDict) {
        // 可以用回溯算法暴力得出

        //以下为动态规划思路
        //完全背包问题（wordDict元素可重复使用），
        //dp[i] 表示 字符串长度为i时，  dp[i]为是否被wordDict元素组成。 返回值求 dp[s.length()]
        boolean[] dp = new boolean[s.length()+1];

        //初始化
        dp[0] = true; // 0长度的字符串 能被wordDict组成。

        //遍历公式： if( s[i,j]在wordDict中 && s[i] == true) s[j] = true
        //遍历顺序：本质上是wordDict元素的组合问题， 所以先遍历背包容量（正序），再遍历物品（正序）
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j <= i; j++) {
                if(wordDict.contains(s.substring(j,i)) && dp[j]) dp[i] = true;
            }
        }
        return dp[s.length()];
    }
}
